29/09/2017
\[ \]
Arrival time: \(a_j\), when customer \(j\) arrives
Service time: \(s_j\), how much time customer \(j\) needs with a server
Departure time: \(d_j\), when customer \(j\) has been served
Waiting time: \(w_j = d_j - a_j - s_j\), how long customer \(j\) waited to be served
\(f_{\delta} / f_s / K / C / n / R\)
\(f_{\delta}\): inter-arrival distribution
\(f_s\): service distribution
\(K\): number of servers
\(C\): capacity of system
\(n\): number of customers
\(R\): service discipline
system utilization: \(\rho = \frac{\mu}{\lambda}\)
The steady state probability of \(N\) customers in a \(M/M/K\) system is,
\[ \begin{align} P(0) &= \left[\frac{ (K \rho)^K}{K! (1 - \rho)} + 1 + \sum_{i=1}^{K-1} \frac{(K \rho)^i}{i!} \right]^{-1} \\ P(N) &= \begin{cases} P(0) \frac{(K \rho)^n }{N!} & \quad N \leq K\\ P(0) \frac{(K \rho)^n }{K! K^{N-K}} & \text{otherwise} \end{cases} , \label{eq:pn} \end{align} \]
R package queuecomputer
Computation time in milliseconds for varying numbers of passengers for each DES/queueing package.
Sutton, C., & Jordan, M. I. (2011). Bayesian inference for queueing networks and modeling of internet services. The Annals of Applied Statistics, 254-282.
Queueing network model of an international airport terminal.
Simulation is used to convert \(\mathbf{(a,s)}\) to departure times \(\mathbf{d}\). \(\mathbf{Z}\) in step 7 is a function of the \(\mathbf{(a,s)}, \mathbf{d}\) and \(\theta_C\). It reflects features such as average waiting time, average queue length and resource utilization.
library(AirportSimulator) suppressPackageStartupMessages(library(dplyr)) airport_simulate() %>% sample_frac()
## # A tibble: 15,602 x 49 ## FlightNo Passengers arrival chocks gate Aus Flight_lag distance ## <chr> <dbl> <dbl> <dbl> <dbl> <dbl> <dbl> <dbl> ## 1 STU374 204 844.81 849.81 7 0.5493974 10 50 ## 2 MMV426 202 475.15 480.15 11 0.1687726 12 100 ## 3 GFG548 188 437.41 442.41 8 0.7446436 9 50 ## 4 RDL588 207 509.19 514.19 8 0.3548210 7 50 ## 5 MGK352 205 873.68 878.68 4 0.2227345 10 25 ## 6 AJQ982 203 843.63 848.63 6 0.2964728 11 50 ## 7 QIH619 199 986.85 991.85 10 0.8941724 13 100 ## 8 MMV426 202 475.15 480.15 11 0.1687726 12 100 ## 9 OLY647 189 596.11 601.11 3 0.3986504 8 25 ## 10 HOC337 230 950.22 955.22 5 0.5917895 15 25 ## # ... with 15,592 more rows, and 41 more variables: walk_imm <dbl>, ## # walk_aerobridge <dbl>, walk_bh <dbl>, walk_quarantine <dbl>, ## # passenger_num <int>, service_aerobridge <dbl>, nationality <fctr>, ## # walk_AC <dbl>, route_prob <dbl>, route_imm <fctr>, service_rate <dbl>, ## # num_baggage <dbl>, route_prob_1_quarantine <dbl>, ## # route_prob_2_quarantine <dbl>, route_baggage <dbl>, service_imm <dbl>, ## # n_bags <int>, route_quarantine <chr>, rate_quarantine <dbl>, ## # service_quarantine <dbl>, service_bags <dbl>, server_imm <list>, ## # server_baggage <list>, server_quarantine <list>, arrive_AC <dbl>, ## # arrive_imm <dbl>, depart_imm <dbl>, arrival_bags <dbl>, ## # depart_bags <dbl>, arrive_bh <dbl>, depart_bh <dbl>, ## # arrive_quarantine <dbl>, depart_quarantine <dbl>, ## # route_imm_true <fctr>, dwell_AC <dbl>, wait_imm <dbl>, ## # dwell_imm <dbl>, wait_bh <dbl>, dwell_bh <dbl>, wait_q <dbl>, ## # dwell_q <dbl>
For many complex models \(f (y|\theta)\) is easy to sample from but difficult or impossible to evaluate. Intuitively we may think that the best way to estimate \(\theta\), based on observed data \(y\), is to take samples from \(f (y|\theta)\) with different values of \(\theta\) until \(x\) “looks like” \(y\).
\[ \begin{align} \widehat{\text{MMD}}^2_b(X,Y|s) &= \frac{1}{m^2} \sum_{i,j = 1}^{m} k(x_i, x_j) \\ &\quad + \frac{1}{n^2} \sum_{i,j = 1}^{n} k(y_i, y_j) - \frac{2}{mn} \sum_{i,j = 1}^{m,n} k(x_i, y_j). \end{align} \]
Gretton, A., Borgwardt, K. M., Rasch, M., Schölkopf, B., & Smola, A. J. (2007). A kernel method for the two-sample-problem. In Advances in neural information processing systems (pp. 513-520).
library(AirportSimulator) true_params <- c(0.2, 20, 1.1, 3.5, 0.8, 3) y <- airport_sim_1(true_params) x <- airport_sim_1(true_params) airport_MMD(y,x, threshold = 6)
## [1] 0.0243735
proposed_params <- c(0.2, 10, 0.5, 3.5, 0.8, 3) x <- airport_sim_1(proposed_params) airport_MMD(y,x, threshold = 6)
## [1] 0.04856347
library(tidyr)
library(ggplot2)
data_frame(y = unlist(y), x = unlist(x), input_output = rep(c("input", "output"), each = 15602)) %>%
gather(key = "key", value = "time", y, x) %>%
ggplot(aes(x = time, col = input_output)) +
geom_density(adjust = 0.0001) +
facet_grid(key ~ .)
ABC posterior distributions.
Distribution of average waiting time for passengers by flight. Resimulations with fixed parameters.
Particle resampling of trajectories with data assimilation.
Anthony Ebert
Supervised by: Kerrie Mengersen, Paul Wu, Fabrizio Ruggeri
Email: ac.ebert@qut.edu.au
Github: AnthonyEbert
Twitter: @ace_ebert
Have a look at the R package queuecomputer
This work is supported by the Australian Research Council Centre of Excellence for Mathematical and Statistical Frontiers (ACEMS).